// 路径压缩 -- 道格拉斯算法
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define limit 0.2 //阈值
typedef struct point
{
    double x, y; //点的坐标
    int tag;     //是否保留 1 保留 0 舍弃
};
//求p3到 p1p2的距离
//max_des 最大点距  max_point 最大点距的点数组下标
void get_max(point p_set[], int left, int right, double &max_des, int &max_point)
{
    point p1, p2;
    p1 = p_set[left];
    p2 = p_set[right];
    double A, B, C;
    A = (p1.y - p2.y) / (sqrt((p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x)));
    B = (p2.x - p1.x) / (sqrt((p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x)));
    C = (p1.x * p2.y - p2.x * p1.y) / (sqrt((p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x)));
    max_des = -1;
    double des;
    for (int i = left; i < right; i++)
    {
        point p3 = p_set[i];
        des = fabs(A * p3.x + B * p3.y + C);
        if (des > max_des)
        {
            max_des = des;
            max_point = i;
        }
    }
}
void d_fun(point p_set[], int left, int right)
{
    //1.递归结束
    if (right - left < 2)
        return;
    //2.找出max_des getmax()
    double max_des;
    int max_point;
    get_max(p_set, left, right, max_des, max_point);
    //3.if (max_des<limit) 点全部舍弃
    if (max_des < limit)
    {
        for (int i = left + 1; i < right; i++)
        {
            p_set[i].tag = 0;
        }
    }
    //4.else 对左右点集进行递归
    else
    {
        d_fun(p_set, left, max_point);
        d_fun(p_set, max_point, right);
    }
}
void douglas(point p_set[], int &n)
{
    //1 douglas算法
    d_fun(p_set, 0, n - 1);
    //对点进行排序(需要进行稳定排序排序前后相同值的相对位置不变) tag为1的放在见面 tag 为0 的放在后面 舍弃tag为0的点
    point *t_set = (point *)malloc(sizeof(point) * n);
    int t = 0;
    for (int i = 0; i < n; i++)
    {
        if (p_set[i].tag == 1)
        {
            t_set[t++] = p_set[i];
        }
    }
    for (int k = 0; k < t; k++)
    {
        p_set[k] = t_set[k];
    }
    n = t;

    int i, j;
    i = 0;
    j = 0;
    while (j < n && i < n)
    {
        while (p_set[i].tag == 1)
            i++;
        while (p_set[j].tag == 0)
            j++;
        if (i < j)
        {
            if (j < n)
            {
                point t_p;
                //交换两个点的信息
                t_p.tag = p_set[i].tag;
                t_p.x = p_set[i].x;
                t_p.y = p_set[i].y;
                //
                p_set[i].tag = p_set[j].tag;
                p_set[i].x = p_set[j].x;
                p_set[i].y = p_set[j].y;
                //
                p_set[j].tag = t_p.tag;
                p_set[j].x = t_p.x;
                p_set[j].y = t_p.y;
                i++;
                j++;
            }
        }
        else
        {
            j = i;
        }
    }
}

int main()
{
    /*******************code*******************/

    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
